/*****************************************************************************
 * heap.h: Public interface for a client heap
 *****************************************************************************
 * Copyright (C) 2012
 *
 * Authors: Dan Larkin <danielhlarkin@gmail.com>
 *          Yonatan Naamad <cached@gmail.com>
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *****************************************************************************/

#ifndef CPM_HEAP
#define CPM_HEAP

typedef struct cpm_heap_node
{
    struct cpm_heap_node *child;
    struct cpm_heap_node *next;
    struct cpm_heap_node *prev;

    void* element;
} cpm_heap_node;
    
typedef struct cpm_heap
{
    int (*less)( void*, void* );
    cpm_heap_node *root;
} cpm_heap;

cpm_heap* cpm_heap_init( int (*less)( void*, void* ) );
cpm_heap_node* cpm_heap_insert( cpm_heap *heap, void *element );
void* cpm_heap_find_min( cpm_heap *heap );
void* cpm_heap_delete_min( cpm_heap *heap );
void* cpm_heap_delete( cpm_heap *heap, cpm_heap_node *node );
void cpm_heap_decrease_key( cpm_heap *heap, cpm_heap_node *node );
cpm_heap_node* cpm_heap_increase_key( cpm_heap *heap, cpm_heap_node *node );
int cpm_heap_empty( cpm_heap *heap );

#endif
